package org.example;

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.function.ToIntFunction;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}
class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        //1.创建一个小根堆
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>(new Comparator() {
            @Override
            public int compare(Object o1, Object o2) {
                ListNode node1 =  (ListNode) o1;
                ListNode node2 =  (ListNode) o2;
                return node1.val - node2.val;
            }
        });
        int k = lists.length;

        //2.把所有的头结点放入小根堆
        for(ListNode head : lists){
            if(head != null) minHeap.offer(head);
        }

        //3.合并K个链表
        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead;
        while(!minHeap.isEmpty()){
            ListNode poll = minHeap.poll();
            cur.next = poll;
            cur = cur.next;
            if(poll.next != null) {
                poll = poll.next;
                minHeap.offer(poll);
            }
        }
        return dummyHead.next;
    }
}


class Solution2 {
    public ListNode mergeKLists(ListNode[] lists) {
        return mergeSort(lists, 0, lists.length - 1);
    }

    private ListNode mergeSort(ListNode[] lists, int l, int r) {
        if(l > r) return null;
        if(l == r) return lists[l];

        //根据中间节点划分左右两个区间
        int mid = (l + r) >> 1;

       ListNode left =  mergeSort(lists, l, mid);
       ListNode right = mergeSort(lists, mid + 1, r);
       return mergeTwoLists(left, right);
    }

    private ListNode mergeTwoLists(ListNode left, ListNode right) {
        ListNode dummyHead = new ListNode(-1);
        ListNode cur1 = left, cur2 = right;
        ListNode cur3 = dummyHead;
        while(cur1 != null && cur2 != null){
            if(cur1.val <= cur2.val){
                cur3.next = cur1;
                cur3 = cur3.next;
                cur1 = cur1.next;
            } else
            {
                cur3.next = cur2;
                cur3 = cur3.next;
                cur2 = cur2.next;
            }
        }
        cur3.next = cur1 != null ? cur1 : cur2;
        return dummyHead.next;
    }

}